package com.cat.chapter055;

/**
 * @author cat
 * @description https://leetcode.cn/problems/max-value-of-equation/
 * @create 2025/7/27 13:40
 * @since JDK17
 */

public class Solution02 {
    static int N = ((int) (1e5 + 10)), h, t;
    static int[] deque = new int[N];
    static int[][] p;
    public int findMaxValueOfEquation(int[][] points, int k) {
        int ans = 0, n = points.length;
        h = t = 0;
        p = points;
        for (int l = 0, r = 0; r < n; r++) {   // [l, r)窗口
            while (h < t && isOk(r)) {
                t--;
            }
            int temp = p[r][0] - p[deque[h]][0];
            if (temp <= k) {  // 求答案
                ans = Math.max(ans, p[r][1] + p[deque[h]][1] + temp);
            } else {    // 没答案
                h++;
            }
            deque[r] = t;
        }

        return ans;
    }
    boolean isOk(int r) {
        return p[r][0] - p[deque[t - 1]][0] + p[r][1] - p[deque[t - 1]][1] > 0;
    }


}
